#include <stdio.h>
#include <stdlib.h>

#define MAX_TREE_SIZE 100  // 定义最大树大小

// 哈夫曼树节点结构定义
typedef struct {
    int weight;  // 节点权值
    int parent, lchild, rchild;  // 父节点、左孩子、右孩子的索引
} HuffmanNode, HuffmanTree[MAX_TREE_SIZE];

// 选择两个权值最小的未被合并的节点
// 选择两个权值最小的未被合并的节点
void selectMin(HuffmanTree tree, int n, int *s1, int *s2) {
    *s1 = *s2 = 0;  // 初始化为0，表示未选中，假设数组索引从1开始使用
    int i;
    // 寻找第一个最小权值的节点
    for (i = 1; i <= n; i++) {
        if (tree[i].parent == 0) { // 只考虑未被合并的节点
            if (*s1 == 0 || tree[i].weight < tree[*s1].weight) {
                *s1 = i;
            }
        }
    }
    // 寻找第二个最小权值的节点
    for (i = 1; i <= n; i++) {
        if (tree[i].parent == 0 && i != *s1) { // 排除已选为最小的*s1节点
            if (*s2 == 0 || tree[i].weight < tree[*s2].weight) {
                *s2 = i;
            }
        }
    }
}


// 构建哈夫曼树的函数
void createHuffmanTree(HuffmanTree tree, int weights[], int n) {
    if (n <= 1) return; // 如果节点数小于等于1，不进行构建
    int m = 2 * n - 1; // 总节点数，包括内部节点
    for (int i = 1; i <= m; ++i) {
        tree[i].parent = tree[i].lchild = tree[i].rchild = 0; // 初始化节点
    }
    for (int i = 1; i <= n; ++i) tree[i].weight = weights[i - 1]; // 加载叶子节点权值

    for (int i = n + 1; i <= m; ++i) {
        int s1, s2;
        selectMin(tree, i - 1, &s1, &s2); // 选择两个最小权值的节点
        tree[s1].parent = tree[s2].parent = i; // 设置这两个节点的父节点
        tree[i].lchild = s1; // 设置左孩子
        tree[i].rchild = s2; // 设置右孩子
        tree[i].weight = tree[s1].weight + tree[s2].weight; // 新节点的权值是两个子节点权值之和
    }
}

// 主函数
int main() {
    int weights[] = {7, 5, 2, 4};  // 权值数组
    HuffmanTree tree; // 哈夫曼树
    int n = sizeof(weights) / sizeof(weights[0]); // 节点数量
    createHuffmanTree(tree, weights, n); // 构建哈夫曼树

    // 打印哈夫曼树的节点信息
    for (int i = 1; i <= 2 * n - 1; i++) {
        printf("Node %d: weight=%d, parent=%d, lchild=%d, rchild=%d\n",
               i, tree[i].weight, tree[i].parent, tree[i].lchild, tree[i].rchild);
    }

    return 0;
}
